package leetcode_400;

import java.math.BigInteger;

/**
 *@author 周杨
 *AdditiveNumber_306 一种新方式的加减运算
 *describe:暴力回溯 AC 22%
 *2018年6月30日 下午5:00:36
 */
public class AdditiveNumber_306 {
	public static void main(String[] args) {
		AdditiveNumber_306 test=new AdditiveNumber_306();
		//System.out.println(test.isAdditiveNumber("112358"));
		System.out.println(test.isAdditiveNumber("199100199"));
	}
	
	public boolean isAdditiveNumber(String num) {
		if(num.length()==0)
			return false;
        return help(num,0,0,0);
    }
	
	/**
	 * describe:回溯法 题目看错了 以为是拆分字符串  其实是拆分字符串序列 可以反复用序列
	 * 2018年6月30日 下午4:28:13
	 * @param num 字符串
	 * @param index 当前遍历值
	 * @param status 0代表前面没有数 1代表前面有一个数了 2代表前面有2个数
	 * @param sum 当前和
	 */
	private boolean help(String num,int index,int status,int sum) {
		if(index==num.length()-1) {//处理最后一个数
			if(status==2)
				if(sum==Integer.valueOf(num.substring(index, index+1)))
					return true;
				else
					return false;
			else 
				return false;
		}
		boolean flag=false;
		char now=num.charAt(index);
		if(status==0) {//前面没有数
			if(now=='0') {
				return help(num,index+1,1,0);
			}
			else {
				for(int i=1;i+index<num.length();++i) {
					flag=help(num,index+i,1,Integer.valueOf
							(num.substring(index,index+i)));
					if(flag)
						return true;
				}
			}
		}
		else if(status==1) {//前面有了数
			if(now=='0') {
				return help(num,index+1,2,sum);
			}
			else {
				for(int i=1;i+index<num.length();++i) {
					flag=help(num,index+i,2,sum+Integer.valueOf
							(num.substring(index,index+i)));
					if(flag)
						return true;
				}
			}
		}
		else {
			if(now=='0') {
				return sum==0;
			}
			else {
				for(int i=1;i+index<num.length();++i) {
					int may=Integer.valueOf(num.substring(index,index+i));
					if(may<sum)
						continue;
					else if(may==sum) {
						if(index+i==num.length()-1)
							return true;
						else
							return help(num,index+i,0,0);
					}
					else
						return false;
				}
			}
		}
		return false;
	}
	
	
	/**
	 * describe:依然是暴力解 dfs思想 AC 20%
	 * 2018年6月30日 下午5:00:13
	 */
	public boolean isAdditiveNumber1(String num) {
	    int len = num.length();
	    for (int i = 1; i <= len / 2; i++) {
	        for (int j = 1; Math.max(i, j) <= len - i - j; j++) {
	            if (isValid(i, j, num)) {
	                return true;
	            }
	        }
	    }
	    return false;
	}
	
	public boolean isValid(int i, int j, String num) {
	    if (num.charAt(0) == '0' && i > 1) return false;
	    if (num.charAt(i) == '0' && j > 1) return false;
	    BigInteger x1 = new BigInteger(num.substring(0, i));
	    BigInteger x2 = new BigInteger(num.substring(i, i + j));
	    String sum;
	    for (int start = i + j; start < num.length(); start += sum.length()) {
	        x2 = x2.add(x1);
	        x1 = x2.subtract(x1);
	        sum = x2.toString();
	        if (!num.startsWith(sum, start)) return false;
	    }
	    return true;
	}
}
